This invention relates to secure communication methods and devices, and more particularly to methods and devices for encryption of data in communication systems.
The proliferation of wireless sensor networks (WSN) in recent years has prompted increased interest in secure communications for embedded devices. Wireless sensor nodes are inherently resource-constrained in terms of processor speed, bandwidth, energy usage, code space, and RAM size. Therefore, there is a need for secure encryption/decryption implementations that can accommodate such constraints, preferably with a small footprint while performing at speeds comparable to the radio transmission bit rate on a low-speed processor.
The Advanced Encryption Standard (AES) became the standard for encryption to protect sensitive information by all U.S. government organizations on May 26, 2002 [4]. Its inclusion in the IEEE 802.15.4 [5] standard as the standard encryption protocol for the ZigBee wireless communication protocol makes AES ideal for use in WSNs. According to the IEEE 802.15.4 specification, Low Rate—Wireless Personal Area Networks (LR-WPAN) have a maximum over the-air data rate of 250 kbps. No known software scheme is able to encrypt data using AES at a rate of 250 kbps or higher. Thus, the maximum data rate cannot be achieved with AES encrypted communication. Moreover, there has been considerable disagreement among various research groups about the performance and memory footprint of AES implementations. The memory footprint consists of RAM usage and ROM usage. RAM is often a highly constrained resource on embedded platforms (e.g., the Crossbow Mica2 mote has 4 KB and the Texas Instruments MSP430 chip has up to 10 KB). The ROM memory is used to hold the program and therefore it is desirable to limit its usage by the cryptographic functions.
Attempts have been made to produce fast implementations of AES. For example, in reference [12] cited in the list of references included herewith, Y. W. Law et al. benchmarked various block ciphers including Rijndael (AES) on a 16-bit MSP430 microcontroller. Their implementation is based on code from the open source OpenSSL library. It is heavily modified and compiled with the commercial IAR Workbench compiler. They have speed-optimized and size-optimized versions of each implementation running in Cipher-Block ChainingMode (CBC), Cipher Feedback Mode (CFB), Output Feedback Mode (OFB) and Counter Mode (CTR). Their estimate shows that AES performs best in OFB mode taking 3127 clock cycles to encrypt a 128-bit block of plaintext while taking up 12860 bytes of code memory (ROM) and 70 bytes of data memory (RAM). Their size-optimized AES implementation takes 4231 clock cycles to encrypt a 128-bit block of plaintext taking up 12616 bytes of ROM and 70 bytes of RAM.
In [14], A. Vitaletti et al. focus on the need for a compact implementation. Their implementation requires 3322 bytes in ROM and 177 bytes in RAM. However, to achieve low code size they have sacrificed performance. Their implementation takes 3.75 ms to encrypt a 128-bit block of plaintext on a 16-Bit MSP430 microcontroller running at 4 MHz.
In [6], D. R. Duh et al. implement AES on a sensor node based on the 8-bit Atmel ATmega 128L microcontroller running at 8 MHz. They based their implementation on Brian Gladman's code that was cited in the AES proposal. Their implementation can reportedly encrypt a 128-bit block of plaintext in 0.857 ms.
Texas Instruments has made available a Zigbee Stack for boards using the MSP430 with a Chipcon CC2420 transceiver chip. Even though the CC2420 has hardware support for AES, the stack includes a software implementation of the AES-128 encryption algorithm.
FIG. 7 and Table 5 herein summarize the published results of each of these implementations and the results obtained during testing by the present inventors.
Advanced Encryption Standard
Rijndael Cipher, developed by Joan Daemen and Vincent Rijmen, was accepted as the Advanced Encryption Standard on Nov. 26, 2001. It is a symmetric-key block cipher with a block length of 128-bits and a flexible key length of 128, 192 or 256 bits. This section gives an overview of how AES works.
Encryption/Decryption Algorithm
A series of permutations and substitutions are applied to the plaintext for encryption. FIG. 1 illustrates the overall structure of the algorithm [13]. There are 4 main transformations used in this process. Each transformation is applied to a 4×4 byte matrix called the State. These transformations are described below:
SubBytes: Each byte in the state is substituted by a byte from a 256-byte look-up table called the s-box.
ShiftRows: The bytes in each of the 4 rows in the state are rotated by (n−1) where n represents the row number from 1 to 4.
MixColumns: The state can be considered to be a 4×4 matrix and this transformation can be achieved by multiplying this matrix by:
         [                            02                          03                          01                          01                                      01                          02                          03                          01                                      01                          01                          02                          03                                      03                          01                          01                          02                      ]  
This multiplication is done in GF (28).1 1All arithmetic in Rijndael is done in a Galois Field with 256 elements.
AddRoundKey: In this transformation, the round key is simply added to the state. In GF (28), adding is equivalent to a bitwise exclusive-or operation.
The encryption process consists of initially applying AddRoundKey and 10, 12 or 14 rounds depending on the length of the key. Each round except the last one consists of applying the 4 transformations to the state. In the last round, only the SubBytes, ShiftRows and AddRoundKey transformations are applied.
The Key Expansion
The cipher key is expanded to generate a different key for each round. Similar to the State, the key is also considered to be a two-dimensional matrix consisting of 4 rows. Each column is considered to be a 4-byte word. The expansion is achieved by applying SubWord and RotWord transformations and addition in GF (28) of RCon[ ], a constant word array. These operations are described below:
SubWord: Similar to the SubBytes transformation, this is done by substituting each byte in the word with a byte from a 256-byte substitution box.
RotWord: This transformation cyclically shifts the bytes of a word one place upwards.
The key expansion differs slightly for 128-, 192- and 256-bit keys, but for AES-128, discussed further herein, the expanded key consists of 176-bytes (44 words). The first 4 words of the expanded key consist of the original cipher key. Every word after that is equal to the sum of the previous word and the word 4 positions earlier. For words in positions that are multiples of 4, the SubWord and RotWord transformations are applied before applying the above described exclusive-or. After the exclusive-or, another exclusive-or with the RCon[ ] associated with the round is applied.
Profiling
Table 1 below is a frequency distribution table of the different transformations in the encryption process. This serves as a good starting point in the analysis of the algorithm for optimization.
TABLE 1Frequency of transformations in applying AES-128 to a single data blockProcedure Times CalledKeyExpand1SubBytes9ShiftRows9MixColumns8AddRoundKey10Brian Gladman's Low-Resource ImplementationUse of Look-Up Tables
Gladman's implementation had three 256-byte look-up tables used for encryption and five 256-byte look-up tables for decryption.
Combination of Transformations
Gladman combined the MixColumns and SubBytes transformations as well as the ShiftRows and SubBytes transformations into two functions. These combinations are possible because the shifting of rows and mixing of columns are always the same and are independent of the contents of the state. A large number of memory moves are eliminated by combining these transformations with the SubBytes transformation.
Tuning Options
Gladman's code has 3 options which can be changed prior to compiling the code. These options are made possible using conditional preprocessor directives and modify the code considerably before compilation. These options can be activated/deactivated by using the #define preprocessor directive. These are briefly described below:
HAVE_MEMCPY: Defining this directs the compiler to take advantage of the memcpy function in the compiler's standard library.
HAVE_UINT32: Defining this directs the compiler to take advantage of 32-bit data types if available on the target platform.
VERSION—1: Defining this makes extensive use of local buffers within functions instead of accessing data through pointers.
IEEE 802.15.4 Security Specification
The IEEE 802.15.4 standard was first released in 2003 and revised in 2006. It includes Wireless Medium Access Control (MAC) as well as Physical layer specifications. Security is specified as part of the MAC sublayer. Since most WSNs fall within the category of LR-WPANs, compliance with this standard ensures reliability, compatibility and scalability of the network. There are a total of 8 security modes of which 4 ensure data confidentiality. These modes are listed in Table 2:
TABLE 2Security modes specified in IEEE 802.15.4LevelAttribute ConfidentialityDescription0x00NoneNONo security0x01MIC-32NOAuth (CBC-MAC) 32 bit MIC0x02MIC-64NOAuth (CBC-MAC) 64 bit MIC0x03MIC-128NOAuth (CBC-MAC) 128 bit MIC0x04ENCYESEnc (Counter mode AES)0x05ENC-MIC-32YESEnc + Auth (CCM-Mode) 32 bit MIC0x06ENC-MIC-64YESEnc + Auth (CCM-Mode) 64 bit MIC0x07ENC-MIC-128YESEnc + Auth (CCM-Mode) 128 bit MIC
All four modes that ensure data confidentiality use AES as the underlying block cipher function. Level 0x04 uses AES in counter mode whereas levels 0x05 through 0x07 use AES in CCM mode. Moreover, CBC-MAC is a cipher-based authentication scheme that in this case, once again, uses AES as the block cipher. For more information on AES modes of operation, refer to [7].
Therefore all security modes (except 0x00) rely on AES as the block cipher with a block length of 128 bits.